package _mst;

import _object.TreeNode;

/**
 * 面试题 04.12. 求和路径
 */
public class T0412 {
    private int sum;
    private int ans;

    public int pathSum(TreeNode root, int sum) {
        this.sum = sum;
        pathSum(root);
        return ans;
    }

    public void pathSum(TreeNode root) {
        if (root == null) return;
        dfs(root, 0);
        pathSum(root.left);
        pathSum(root.right);
    }

    private void dfs(TreeNode node, int curSum) {
        if (node == null) return;
        if (curSum + node.val == sum) ans++;
        dfs(node.left, curSum + node.val);
        dfs(node.right, curSum + node.val);
    }
}
